package 二叉树高频题目_上_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelOrderSerializeAndDeserialize {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(Integer val) {
            this.val = val;
        }
    }

    // 提交这个类
    // 按层序列化
    public class Codec {
        public int MAXN = 10001;
        public TreeNode[] queue = new TreeNode[MAXN];
        public int l, r;

        public String serialize(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            if(root != null){
                l = 0;
                r = 0;
                queue[r++] = root;
                stringBuilder.append(root.val + ",");
                while(l < r){
                    root = queue[l++];
                    if(root.left != null){
                        stringBuilder.append(root.left.val + ",");
                        queue[r++] = root.left;
                    }else {
                        stringBuilder.append("#,");
                    }
                    if(root.right != null){
                        stringBuilder.append(root.right.val + ",");
                        queue[r++] = root.right;
                    }else {
                        stringBuilder.append("#,");
                    }
                }
            }
            return stringBuilder.toString();
        }

        public TreeNode deserialize(String data) {
            if(data.equals("")){
                return null;
            }
            String[] nodes = data.split(",");
            // 字符串数组 nodes 的索引
            int index = 0;
            l = 0;
            r = 0;
            TreeNode root = generate(nodes[index++]);
            queue[r++] = root;
            while (l < r){
                TreeNode cur = queue[l++];
                cur.left = generate(nodes[index++]);
                cur.right = generate(nodes[index++]);

                if(cur.left != null){
                    queue[r++] = cur.left;
                }
                if(cur.right != null){
                    queue[r++] = cur.right;
                }
            }
            return root;
        }

        public TreeNode generate(String val){
            return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));
        }
    }
}
